2. TVORBA ALGORITMOV
Program je vlastne postupnosť príkazov v strojovom kóde. Ale prečo píšeme takéto postupnosti a podľa čoho sa rozhodujeme, že aká má byť táto postupnosť? Počítač môže byť užitočnou pomôckou a pomocou dobre napísaného programu množstvo a kvalita odvedenej práce sa môže viacnásobne zvýšiť. Často musíme riešiť úlohy podľa možnosti rýchlo a dobre. Možnosť máme: vyriešme to pomocou počítača! Keď človek sa učí svoj prvý programovací jazyk, zdá sa mu, že najťažšie v programovaní je výber príkazov z programovacieho jazyka. Ale nie je to tak. Najťažšie je vymyslieť spôsob riešenia, čo prakticky vôbec nezávisí od programovacieho jazyka. Ak sme určili spôsob riešenia úlohy, potom vytvoriť zdrojový program v ľubovolnom programovacom jazyku už je "hračkou". Týmto jazykom môže byť Pascal, Cobol, C alebo Clipper.
2.1 Algoritmus
Pri riešení konkrétneho problému doporučuje sa zabudnúť na konkrétny programovací jazyk a treba rozmýšľať nad krokmi, ktoré treba urobiť, aby sme daný problém vyriešili. Najlepšie je, ak človek napíše inštrukcie, ako keby úlohu chcel vyriešiť pomocou nejakého rozumného tvora a nie pomocou počítača. Samozrejme inštrukcie môžu obsahovať podmienky, opakovania. Množinu tých príkazov, ktoré vedú k vyriešeniu danej úlohy, nazývame algoritmom. S algoritmami aj v bežnom živote sa stretávame na každom kroku. Inštrukcie môžeme zadať mnohými spôsobmi, napr. ústne, kresbou, písomne, po slovensky, po anglicky alebo pomocou programovacieho jazyka.
Algoritmus je teda cesta k riešeniu vzniknutého problému. Nech je napríklad našou úlohou zohnať 5 fliaš marhuľového lekváru. K tomu aby sme úlohu splnili, musíme naplánovať činnosti, ktoré musíme urobiť. Môže sa stať, že algoritmus bude postupnosťou za sebou vykanávaných elementárnych činností ako napr.:
Choď k babičke!
Popros od nej 5 fliaš marhuľového lekváru!
Prines lekvár domov!
Môže sa stať, že riešenie v niektorých bodoch sa nedá dopredu určiť ale podľa podmienok dokážeme vybrať vhodný ďalší postup riešenia úlohy (selekcia). Napr.:
Choď k babičke!
Ak je doma, potom
Pýtaj od nej 5 fliaš marhuľového lekváru!
inak
Kúp v obchode 5 fliaš marhuľového lekváru!
Prines lekvár domov!
Môže sa stať, že niektorú činnosť nevieme vykonať "naraz" a k vykonaniu potrebujeme uskutočniť ďalšie akcie. V takom prípade túto činnosť musíme rozobrať na elementárne činnosti. Takou môže byť aj príkaz " Choď k babičke!":
Choď na ulicu!
Počkaj na autobus!
Ak príde autobus behom 10 minút, potom
Nastúp do autobusu! (1)
inak
Choď pešo!
Zazvoň!
Aj činnosť "Kúp v obchode 5 fliaš marhuľového lekváru!" môžeme upresniť napr. nasledovne:
Choď do obchodu!
Zober z police 5 fliaš marhuľového lekváru!
Zaplať za lekvár!
Polož lekvár do tašky!
Môže sa stať, že niektorú činnosť musíme viackrát opakovať (iterácia). Môže sa stať, že počet opakovaní poznáme, ale môže sa stať, že opakovanie je viazané na určitú podmienku. Napr. činnosť "Zober z police 5 fliaš marhuľového lekváru!" pozostáva z 5 rovnakých činností (5 krát sa opakuje):
Urob 5 krát!
Zober z police jednu fľašu lekváru!
Polož lekvár do tašky!
Takúto opakovanú činnosť zvykneme volať cyklom. Podľa výkladových slovníkov význam slova cyklus je: kolobeh, úsek, takt. Vo výpočtovej technike pod cyklom chápeme celú cyklicky vykonávaný dej a túto opakovanú činnosť nazývame telom cyklu. V literatúre pojem cyklu a tela cyklu sa často mieša. Telom cyklu príkazu "Zober z police 5 fliaš marhuľového lekváru!" je činnosť vzatie jednej fľaše lekváru z police a položenie tejto fľaše do košíka. Počet opakovaní poznáme - činnosť musíme 5 krát opakovať. Neuvažujeme možnosť, že na polici je menej fliaš.
Aj celý príkaz "Kúp v obchode 5 fliaš marhuľového lekváru!" môže byť iteráciou. Ak za každú cenu musíme kúpiť lekvár, potom musíme byť pripravení aj na ten prípad, keď obchod je zatvorený, alebo nie je v obchode 5 fliaš lekváru (pre jednoduchosť menej ako 5 fliaš nekupujeme v obchode). V takom prípade sa môže stať, že budeme musieť ísť do viacero obchodov. Musíme chodiť po obchodoch do tej doby, kým nedostaneme 5 fliaš lekváru. Telom cyklu v tomto prípade je návšteva obchodov a prípadne aj nákup lekváru. Z cyklu iba v tom prípade môžeme odísť, ak sme kúpili lekvár. Podmienku ukončenia cyklu nazývame podmienkou cyklu. Teda pred opustením cyklu musíme kúpiť lekvár a až potom môžeme ukončiť cyklus. Ten cyklus v ktorom podmienka sa testuje po vykonaní príkazov tela cyklu sa nazýva vzadu testovaným cyklom. V tomto prípade telo cyklu sa vždy aspoň raz vykoná (aspoň do jedného obchodu určite vojdeme):
Choď do obchodu!
Ak je lekvár, potom
Kúp v obchode 5 fliaš lekváru!
Vyššie uvedené činnosti opakuj do tej doby, kým nedostaneš 5 fliaš lekváru!
V prípade vpredu testovaného cyklu podmienka sa overuje vždy pred vykonaním príkazov tela cyklu. V tomto prípade sa môže stať, že príkazy tela cyklu sa nevykonajú ani raz. Takým je napr. príkaz: "Choď do každého obchodu v ulici!". Ak v ulici nie je ani jeden obchod, potom zostanem doma.
Štruktúru algoritmov tvoria sekvencie (postupnosti) príkazov, selekcie (podmienky) a iterácie (cykly), ktoré môžu byť do seba vložené aj viacúrovňovo. Vloženými cyklami sú napr. "Choď do každého obchodu v okolí a všade spočítaj koľko fliaš marhuľového lekváru sa nachádza na poličke. Vonkajším cyklom je návšteva obchodov a vnútorným - spočítanie počtu fliaš. Všimnite si, že pri zápise na papier štruktúry zdôrazňujeme tým, že posunieme ich vpravo!
Sú také algoritmy, kde súbežne sa môžu vykonávať činnosti. napr. príkaz: "Každý prinesie 5 fliaš lekváru!" je taký, viacero ľudí nakupuje. Pozor, takýto príkaz dokáže spracovať iba počítač s viacerými procesormi. Väčšina počítačov má iba jeden procesor, a ten nie je schopný vykonávať súbežne viacero príkazov a preto s takými algoritmami sa zaoberať nebudeme. Jednoprocesorové počítače dokážu vykonávať vždy iba jeden príkaz a až keď ten ukončia - môžu spracovať ďalší.
V prípade spracovania úlohy na počítači naše vyššie uvedené nepresné definície algoritmu nie sú postačujúce. V takýchto prípadoch algoritmus musí byť jednoznačným, presným a vykonávateľným krok za krokom. Nemôžu byť dopredu nepredvídané prekážky. V prípade počítača - vykonávateľ (teda procesor) nemá úsudok, a teda nevie spracovať také príkazy, ktoré nie sú jednoznačné, neisté. Čo má napríklad robiť náš vykonávateľ v prípade príkazu "Popros od nej 5 fliaš marhuľového lekváru!" (má sa na mysli od babičky), ak babička nie je doma? Pre vykonávateľa v tomto prípade daný príkaz nie je vykonateľný. Alebo si všimneme podrobnejšie algoritmus (1). Predpokladajme, že čakám na autobus. Keď algoritmus overuje podmienku "Ak", potom už na predchádzajúci príkaz "Čakaj na autobus!" sa nemôže vrátiť. Nie je jasné ako dlho sa musí čakať na autobus. V ľubovolnom algoritme po rozhodnutí podmienky sa môžeme vrátiť na predchádzajúci príkaz (ak sme ho jednoznačne definovali ako opakujúcu sa činnosť). V našom prípade štruktúra zápisu umožňuje riešiť úlohu pomocou selekcie. Opakovanú činnosť musíme jednoznačne definovať. Správne túto časť algoritmu sme mali zapísať nasledovne:
Začína sa cyklus:
Čakaj na autobus, medzitým sa pozeraj na hodinky a na autobus!
Toto rob, kým nepríde autobus alebo kým neuplynie 10 minút!
Koniec cyklu
Ak si preto prestal čakať, že prišiel autobus, potom
Nastúp do autobusu!
inak
Choď pešo!
Pre výsledný zápis algoritmu budeme používať programovací jazyk Pascal. Algoritmus, napísaný pre počítač pochopiteľnom jazyku, sa nazýva programom. Preto počítačový jazyk sa nazýva programovacím jazykom.
Najpodstatnejšie vlastnosti a požiadavky na algoritmus resp. program môžeme zhrnúť v nasledujúcich bodoch:
- Algoritmus pozostáva z krokov (elementárnych činností, inštrukcií, príkazov). Vykonávanie algoritmov sa uskutočňuje po krokoch. Takto popísanú postupnosť príkazov nazývame postupom (procesom). V prípade počítača - vykonávateľom je centrálna jednotka, t.j. procesor.
- Každý krok musí byť jednoznačne uskutočniteľný. Vykonávateľa v algoritme musíme už vopred pripraviť na všetky možné prípady. Vykonávateľ po každom kroku musí dokázať jednoznačne určiť, ktorý krok nasleduje.
- V algoritme sa môžeme odvolávať aj na zložitejšie kroky, ktorých podrobnejší popis sa uvedie neskôr. Hĺbka zjemňovania závisí od možností programovacieho jazyka a od jeho elementárnych činností, príkazov. Elementárne činnosti sú už vykonávateľné - ich nerozoberáme na jednoduchšie.
- Vykonávanie činnosti vždy má predmet. Treba mať niečo, na čom sa budú vykonávať príkazy. Predmetmi príkazu "Pýtaj 5 fliaš marhuľového lekváru!" sú osoba, ktorá pýta, babička a marhuľový lekvár. Tieto "predmety" v programovaní nazývame údajmi. Údaje majú vlastnosti. Pri príprave algoritmu berieme do úvahy iba tie údaje a tie ich vlastnosti, ktoré sú potrebné pri riešení úlohy. Túto výberovú, zjednodušujúcu činnosť nazývame abstrakciou.
- Vykonávateľné príkazy musia mať nejaký cieľ. Počas vykonávania príkazov musí nastať nejaká zmena. Vo všeobecnosti sa menia niektorí vlastnosti údajov napr. miesto, kde sa nachádza marhuľový lekvár - prejde od babičky ku prosiacej osobe.
Tvrdenie "Chutný marhuľový lekvár" nie je príkazom, "chutný" môže byť nanajvýš vlastnosťou údaja.
- Algoritmus má vstupné údaje (input), ktoré použije. V našom príklade vstupným údajom je babičkin lekvár alebo lekvár z niektorého obchodu. Úlohou nášho algoritmu je aby lekvár sa dostal na cieľové miesto (na stôl toho, kto vydal daný príkaz).
- Algoritmus musí vytvoriť aspoň jeden výstupný údaj (output). Ten proces, ktorý vytvára brilantné veci, ale nekomunikuje s okolitým svetom, podľa definície nie je algoritmom. V našom príklade výstupným údajom je niekde vstupujúci marhuľový lekvár.
- Algoritmus musí byť riešiteľným pomocou konečného počtu krokov. To znamená, že človek, ktorý píše algoritmus riešenia príkladu túto svoju činnosť prv alebo neskôr ukončí. To znamená, že úlohu získania marhuľového lekváru musíme dokázať vyriešiť konečným počtom krokov. Vykonávanie algoritmu, t.j. program, nemusí sa vždy ukončiť konečným počtom krokov. Marhuľový lekvár sa pravdepodobne v konečnom čase dostane na stôl, ale sú aj nekonečné regulačné systémy. Napr. umelý dýchací prístroj musí pracovať stále, ak treba 100 rokov alebo aj dlhšie. Vopred určiť sa to nedá. Alebo ďalší príklad - dispečing letiska. Bolo by veľmi nepríjemné, keby prestal fungovať práve vtedy, keď sedíme v jednom z ich lietadiel.
- Algoritmus musí byť účinný! Príkazy musia byť jasnými, presnými, jednoduchými a rýchlo vykonávateľnými!
- Algoritmus musíme tak navrhnúť, aby bol nepokaziteľným.
Algoritmus musí byť takým, aby bežiaci program maximálne bral do úvahy potreby užívateľa. Musí byť užívateľsky prítulným!
|